# -*- coding:utf-8 -*-
'''
从上往下打印出二叉树的每个节点，同层节点从左至右打印。

'''
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    # BFS广度优先搜索
    def PrintFromTopToBottom(self, root):
        # write code here
        if not root:
            return []
        currentStack = [root]
        res = []
        while currentStack:
            nextStack = []
            # 存入当前栈的val同时将左右子树存入下一个临时栈
            for i in currentStack:
                if i.left: nextStack.append(i.left)
                if i.right: nextStack.append(i.right)
                res.append(i.val)
            currentStack = nextStack
        return res